Exercise: Graphs - Data Structures with Generic Types in Python

Task#

A universal sink in a graph $G$ is a vertex that is the target of $n − 1$ edges and the source of no edges. Design and implement an algorithm that tests if a graph $G$ , represented as an AdjacencyMatrix, has a universal sink. Your algorithm should run in $O(n)$ time.

Sample input

The sample input will be as follows:

(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)

Expected output

The expected output will be as follows:

Universal Sink not found.
Vertex 4 is a Universal Sink in graph.

main.py

utils.py

from utils import new_boolean_matrix
# MAin class
class AdjacencyMatrix:
    def __init__(self, n):
        self.n = n
        self._initialize()
    # Initialize function   
    def _initialize(self):
        self.a = new_boolean_matrix(self.n, self.n)  
    # Function to add edges
    def add_edge(self, i, j):
        self.a[i][j] = True
    # Function to remove edges
    def remove_edge(self, i, j):
        self.a[i][j] = False
    # Function to return edges
    def has_edge(self, i, j):
        return self.a[i][j]
    # Function to return out edge
    def out_edges(self, i):
        edges = []
        for j in range(self.n):
            if self.a[i][j]:
                edges.append(j)
        return edges
    # Function to return in edge
    def in_edges(self, i):
        edges = []
        for j in range(self.n):
            if self.a[j][i]:
                edges.append(j)

Enter to Rename, Shift+Enter to Preview

Implementation to find universal sink in a graph